/*************************************************************
 * 
 * CopyRight(c)2007, http://www.moorwind.com/
 * email:ezhung@gmail.com
 * for free, but a email permission would be nice
 * 
 ************************************************************/
package kono.utils.collections
{
	import kono.utils.BTnode;
	
	//二叉查找树（BST）， binary search tree （BST）
	public class BStree implements Icollection
	{
		//二叉查找树根结点， the root node of the binary search tree
		private var tree:BTnode;
		
		//查找判断的依据函数，
		//the compare function will use to confirm that the left child's data is less than the current data,
		//while the right child's data is greater than the current data
		private var compare:Function;
		
		//默认的判断函数判读的依据是BST存储了整数， default function used for the integer comparing
		public function BStree(compareTo:Function = null)
		{
			tree = null;
			if(compareTo == null)
			{
				compare = function(a:Number, b:Number):int
				{
					return int(a - b);
				}
			}
			else
			{
				compare = compareTo;
			}			
		}
		
		//增加一个数据到BST， add a new data to BST
		public function add(data:*):void
		{
			var cursor:BTnode = tree;
			var done:Boolean = true;
			if(!tree)
			{
				tree = new BTnode(data);
			}
			else
			{
				while(done)
				{
					if(compare(data, cursor.nodeData) <= 0)
					{
						if(cursor.leftChild)
						{
							cursor = cursor.leftChild;
						}
						else
						{
							cursor.leftChild = new BTnode(data);
							done = false;
						}
					}
					else
					{
						if(cursor.rightChild)
						{
							cursor = cursor.rightChild;
						}
						else
						{
							cursor.rightChild = new BTnode(data);
							done = false;
						}
					}					
				}
			}
		}
		
		//从BST中删除一个指定数据，  remove a given data from the BST;
		//@ target： 要删除的数据，如果删除成功返回true，失败或未找到返回false，
		//@ target： to remove from the BST, return true if success, and return false if failed or can not find it in the BST
		public function remove(target:*):Boolean
		{
			var cursor:BTnode = tree;
			var parentCursor:BTnode = null;
			var t:int;
			while(cursor)
			{
				t = compare(target, cursor.nodeData)
				if(t == 0)
				{
					if(cursor == tree && cursor.leftChild == null)
					{
						tree = tree.rightChild;
						return true;
					}
					if(cursor.leftChild == null)
					{
						if(cursor == parentCursor.leftChild)
						{
							parentCursor.leftChild = cursor.rightChild;
							return true;
						}
						else
						{
							parentCursor.rightChild = cursor.leftChild;
							return true;
						}
					}
					else
					{
						cursor.nodeData = cursor.leftChild.rightMostData;
						cursor.leftChild.removeRightMost();
						return true;
					}				
				}					
				else
				{
					parentCursor = cursor;
					cursor = t < 0 ? cursor.leftChild : cursor.rightChild;
				}
			}
			return false;
		}
		
		//清空BST， clear all the items in the BST
		public function clear():void
		{
			tree = new BTnode(null);
			tree = null;
		}
		
		//返回BST中包含的结点， get the total number in the BST
		public function get size():uint
		{
			return BTnode.getSize(tree);
		}
		
		//中序转换结点数据到array中， write all of the data in the BST into a Array
		public function toArray():Array
		{
			var a:Array = new Array();
			var inorder:Function = function (node:BTnode):void
			{
				a.push(node.nodeData);
			}
			tree.inorderPrint(inorder);
			return a;
		}
		
		//判断BST是否包含给定数据， check if the BST contains the given item
		public function contains(item:*):Boolean
		{
			var cursor:BTnode = tree;
			var t:int;
			while(cursor)
			{
				t = compare(item, cursor.nodeData)
				if(t == 0) 
					return true;
				else
				{
					cursor = t < 0 ? cursor.leftChild : cursor.rightChild;
				}
			}
			return false;
		}
		
		//打印BST结构， print the BST's frame
		public function print():void
		{
			tree.print(2);
		}
		
		//返回BST的信息， return a string representing the BST
		public function toString():String
		{
			return "[BStree, size=" + size + "]";
		}
	}
}